package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 998. 最大二叉树 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/17 13:25
 */
public class InsertIntoMaxTree {


    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root.val < val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        find(root, root.right, val);
        return root;
    }

    private void find (TreeNode last, TreeNode node, int val) {
        if (node == null) {
            last.right = new TreeNode(val);
            return;
        }
        if (node.val >= val) {
            find(node, node.right, val);
        } else {
            TreeNode no = new TreeNode(val);
            last.right = no;
            no.left = node;
        }
    }

}
